package com.gjx.leetcode;

//96. 不同的二叉搜索树
//给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
//
//示例:
//
//输入: 3
//输出: 5
//解释:
//给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
//
//   1         3     3      2      1
//    \       /     /      / \      \
//     3     2     1      1   3      2
//    /     /       \                 \
//   2     1         2                 3




public class Solution096 {
	public int numTrees(int n) {
        if (n < 1) {
        	return 0;
        }
        
        int[][] dp = new int[n+1][n+1];
        
        return dfs(1, n, dp);
        
    }
	
	
	private int dfs(int start, int end, int[][] dp) {
		if (start > end) {
			return 1;
		} else if (start == end) {
			return 1;
		} else if (dp[start][end] != 0) {
			return dp[start][end];
		}
		
		int res = 0;
		
		for (int i=start; i<=end; i++) {
			res += dfs(start, i-1, dp) * dfs(i+1, end, dp);
		}
		dp[start][end] = res;
		return res;
	}
	
	
	public static void main(String[] args) {
		new Solution096().numTrees(3);
	}
}
